package algorithm.leetcode.I401to600;

import java.util.Arrays;

/**
 * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
 * 这个问题和Q70不一样的地方在于,爬楼梯的求解是求排列数
 * 本题和377不一样的地方在于前者是求组合数,后者是排列数
 * 而这个题是求组合数
 *
 * 这是一个完全背包问题,即每件物品不再有一个的上限,而是无穷多个
 *
 * 正确的子问题定义应该是，problem(k,i) = problem(k-1, i) + problem(k, i-k)
 * 即前k个硬币凑齐金额i的组合数等于前k-1个硬币凑齐金额i的组合数加上在原来i-k的基础上使用硬币的组合数。
 * 说的更加直白一点，那就是用前k的硬币凑齐金额i，要分为两种情况考虑，一种是没有用前k-1个硬币就凑齐了，一种是前面已经凑到了i-k，现在就差第k个硬币了。
 */


// 01背包问题和完全背包问题的区别
// 01背包问题: dp[i][j] = f( dp[i-1][j], dp[i-1][j-w[i]], v[i] ), 完全不用第i个选项和用1次第i个
// 完全背包问题: dp[i][j] = f( dp[i-1][j], dp[i][j-w[i]], v[i] ), 完全不用第i个选项和用无数次第i个,只要容量够
//
//   0 1 2 3 4 5
// 0 1
// 1 1 1 1 1 1 1
// 2 1 1 2 2 3 3
// 5 1 1 2 2 3 4

public class Q518 {

    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length+1][amount+1];
        dp[0][0] = 1;

        // 先横向遍历,在纵向遍历
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                if (j-coins[i-1] >= 0) dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[coins.length][amount];
    }

    // 优化一下空间复杂度
    public int change2(int amount, int[] coins) {
        Arrays.sort(coins);
        int[] dp = new int[amount+1];
        dp[0] = 1;

        // 先横向遍历,在纵向遍历
        for (int i = 1; i <= coins.length; i++) {
            int[] backup = dp;
            dp = new int[amount+1];
            for (int j = 0; j <= amount; j++) {
                if (j-coins[i-1] >= 0) dp[j] = backup[j] + dp[j-coins[i-1]];
                else dp[j] = backup[j];
            }
        }
        return dp[amount];
    }

}
